package com.example.git;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SimpleDiff {

    public static void main(String[] args) {
//        List<String> oldLines = Arrays.asList(
//            "foo",
//            "bar",
//            "hello",
//            "world",
//            "done"
//        );
//
//        List<String> newLines = Arrays.asList(
//            "foo",
//            "bar",
//            "hi",
//            "world",
//            "done"
//        );

        List<String> oldLines = Arrays.asList(
            "A", "B", "C", "D", "G", "H"
        );

        List<String> newLines = Arrays.asList(
            "A", "E", "D", "F", "H", "R"
        );

        List<String> diff = diffLines(oldLines, newLines);
        diff.forEach(System.out::println);
    }

    // 主函数：基于 LCS 输出增删 diff
    public static List<String> diffLines(List<String> a, List<String> b) {
        int[][] lcs = computeLCSMatrix(a, b);
        List<String> result = new ArrayList<>();
        backtrackDiff(a, b, a.size(), b.size(), lcs, result);
//        Collections.reverse(result); // 反转回正确顺序
        return result;
    }

    // LCS 动态规划
    private static int[][] computeLCSMatrix(List<String> a, List<String> b) {
        int[][] dp = new int[a.size() + 1][b.size() + 1];
        for (int i = 1; i <= a.size(); i++) {
            for (int j = 1; j <= b.size(); j++) {
                if (a.get(i - 1).equals(b.get(j - 1))) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp;
    }

    // 从 LCS 矩阵反推 diff
    private static void backtrackDiff(List<String> a, List<String> b, int i, int j, int[][] dp, List<String> result) {
        if (i > 0 && j > 0 && a.get(i - 1).equals(b.get(j - 1))) {
            backtrackDiff(a, b, i - 1, j - 1, dp, result);
            result.add("  " + a.get(i - 1)); // unchanged
        } else if (j > 0 && (i == 0 || dp[i][j - 1] >= dp[i - 1][j])) {
            backtrackDiff(a, b, i, j - 1, dp, result);
            result.add("+ " + b.get(j - 1)); // added
        } else if (i > 0 && (j == 0 || dp[i][j - 1] < dp[i - 1][j])) {
            backtrackDiff(a, b, i - 1, j, dp, result);
            result.add("- " + a.get(i - 1)); // removed
        }
    }
}
